{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Parsing A Boolean Expression"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #recursion #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #递归 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: parseBoolExpr"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #解析布尔表达式"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>布尔表达式</strong> 是计算结果不是 <code>true</code> 就是 <code>false</code> 的表达式。有效的表达式需遵循以下约定：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>'t'</code>，运算结果为 <code>true</code></li>\n",
    "\t<li><code>'f'</code>，运算结果为 <code>false</code></li>\n",
    "\t<li><code>'!(subExpr)'</code>，运算过程为对内部表达式 <code>subExpr</code> 进行 <strong>逻辑非</strong>（NOT）运算</li>\n",
    "\t<li><code>'&amp;(subExpr<sub>1</sub>, subExpr<sub>2</sub>, ..., subExpr<sub>n</sub>)'</code>，运算过程为对 2 个或以上内部表达式 <code>subExpr<sub>1</sub>, subExpr<sub>2</sub>, ..., subExpr<sub>n</sub></code> 进行 <strong>逻辑与</strong>（AND）运算</li>\n",
    "\t<li><code>'|(subExpr<sub>1</sub>, subExpr<sub>2</sub>, ..., subExpr<sub>n</sub>)'</code>，运算过程为对 2 个或以上内部表达式 <code>subExpr<sub>1</sub>, subExpr<sub>2</sub>, ..., subExpr<sub>n</sub></code> 进行 <strong>逻辑或</strong>（OR）运算</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个以字符串形式表述的&nbsp;<a href=\"https://baike.baidu.com/item/%E5%B8%83%E5%B0%94%E8%A1%A8%E8%BE%BE%E5%BC%8F/1574380?fr=aladdin\" target=\"_blank\">布尔表达式</a> <code>expression</code>，返回该式的运算结果。</p>\n",
    "\n",
    "<p>题目测试用例所给出的表达式均为有效的布尔表达式，遵循上述约定。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>expression = \"&amp;(|(f))\"\n",
    "<strong>输出：</strong>false\n",
    "<strong>解释：</strong>\n",
    "首先，计算 |(f) --&gt; f ，表达式变为 \"&amp;(f)\" 。\n",
    "接着，计算 &amp;(f) --&gt; f ，表达式变为 \"f\" 。\n",
    "最后，返回 false 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>expression = \"|(f,f,f,t)\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>计算 (false OR false OR false OR true) ，结果为 true 。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>expression = \"!(&amp;(f,t))\"\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>\n",
    "首先，计算 &amp;(f,t) --&gt; (false AND true) --&gt; false --&gt; f ，表达式变为 \"!(f)\" 。\n",
    "接着，计算 !(f) --&gt; NOT false --&gt; true ，返回 true 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= expression.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>expression[i]</code> 为 <code>'('</code>、<code>')'</code>、<code>'&amp;'</code>、<code>'|'</code>、<code>'!'</code>、<code>'t'</code>、<code>'f'</code> 和 <code>','</code> 之一</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [parsing-a-boolean-expression](https://leetcode.cn/problems/parsing-a-boolean-expression/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [parsing-a-boolean-expression](https://leetcode.cn/problems/parsing-a-boolean-expression/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"&(|(f))\"', '\"|(f,f,f,t)\"', '\"!(&(f,t))\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        stk = []\n",
    "        for c in expression:\n",
    "            if c == ',':\n",
    "                continue\n",
    "            if c != ')':\n",
    "                stk.append(c)\n",
    "                continue\n",
    "            t = f = 0\n",
    "            while stk[-1] != '(':\n",
    "                if stk.pop() == 't':\n",
    "                    t += 1\n",
    "                else:\n",
    "                    f += 1\n",
    "            stk.pop()\n",
    "            op = stk.pop()\n",
    "            if op == '!':\n",
    "                stk.append('t' if f == 1 else 'f')\n",
    "            elif op == '&':\n",
    "                stk.append('t' if f == 0 else 'f')\n",
    "            elif op == '|':\n",
    "                stk.append('t' if t else 'f')\n",
    "        return stk[-1] == 't'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "      stack = []\n",
    "      mapping = {\"f\": False, \"t\": True}\n",
    "      for ch in expression:\n",
    "        if ch in mapping:\n",
    "          stack.append(mapping[ch])\n",
    "        elif ch == \",\": continue\n",
    "        elif ch != \")\":\n",
    "          stack.append(ch)\n",
    "        else:\n",
    "          andRes, orRes = True, False\n",
    "          while stack[-1] != \"(\":\n",
    "            cur = stack.pop()\n",
    "            andRes &= cur\n",
    "            orRes |= cur\n",
    "          stack.pop()\n",
    "          if stack[-1] == \"!\":\n",
    "            stack[-1] = not andRes\n",
    "          elif stack[-1] == \"&\":\n",
    "            stack[-1] = andRes\n",
    "          else:\n",
    "            stack[-1] = orRes\n",
    "      return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        stack = []\n",
    "\n",
    "        for ch in expression:\n",
    "            if ch in 'tf!&|':\n",
    "                stack.append(ch)\n",
    "            elif ch == ')':\n",
    "                t,f = 0, 0\n",
    "\n",
    "                while stack[-1] in 'tf':\n",
    "                    t += stack[-1] == 't'\n",
    "                    f += stack[-1] == 'f'\n",
    "                    stack.pop()\n",
    "\n",
    "                match stack.pop():\n",
    "                    case '!':\n",
    "                        c = 't' if f else 'f'\n",
    "                    case '&':\n",
    "                        c = 'f' if f else 't'\n",
    "                    case '|':\n",
    "                        c = 't' if t else 'f'\n",
    "                stack.append(c)\n",
    "\n",
    "        return stack[0] == 't'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        def calc(l:list,s:str) -> str:\n",
    "            if s == '&':\n",
    "                res = 't'\n",
    "                for i in l1:\n",
    "                    if i == 'f':\n",
    "                        res = 'f'\n",
    "                        break\n",
    "            elif s == '|':\n",
    "                res = 'f'\n",
    "                for i in l1:\n",
    "                    if i == 't':\n",
    "                        res = 't'\n",
    "                        break\n",
    "            else:\n",
    "                if l1[0] == 't':\n",
    "                    res = 'f'\n",
    "                else:\n",
    "                    res = 't'\n",
    "            return res\n",
    "        stack = []\n",
    "        for i in range(len(expression)-1,-1,-1):\n",
    "            if expression[i] == \")\" or expression[i] in ['t','f']:\n",
    "                stack.append(expression[i])\n",
    "            elif expression[i] == ',':\n",
    "                continue\n",
    "            elif expression[i] == '(':\n",
    "                l1 = []\n",
    "                while stack[-1] != ')':\n",
    "                    l1.append(stack.pop())\n",
    "                stack.pop()\n",
    "            else:\n",
    "                stack.append(calc(l1,expression[i]))\n",
    "        return True if stack[0] == 't' else False\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        nums = []\n",
    "        ops = []\n",
    "\n",
    "        def calc(a, b, op):\n",
    "            x, y = a == 't', b == 't'\n",
    "            ans = x & y if op == '&' else  x | y\n",
    "            return 't' if ans else 'f'\n",
    "\n",
    "        for c in expression:\n",
    "            if c == ',':\n",
    "                continue\n",
    "            elif c in 'ft':\n",
    "                nums.append(c)\n",
    "            elif c in '!&|':\n",
    "                ops.append(c)\n",
    "            elif c == '(':\n",
    "                nums.append('-')\n",
    "            elif c == ')':\n",
    "                cur = ' '\n",
    "                op = ops.pop()\n",
    "                while nums and nums[-1] != '-':\n",
    "                    top = nums.pop()\n",
    "                    if cur == ' ':\n",
    "                        cur = top\n",
    "                    else:\n",
    "                        cur = calc(cur, top, op)\n",
    "                if op == '!':\n",
    "                    cur = 't' if cur == 'f' else 'f'\n",
    "                nums.pop()\n",
    "                nums.append(cur)\n",
    "        \n",
    "        return nums[-1] == 't'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "\n",
    "        st = []\n",
    "\n",
    "        for c in expression:\n",
    "            if c == ',':\n",
    "                continue\n",
    "            if c != ')':\n",
    "                st.append(c)\n",
    "                continue\n",
    "            t, f = 0, 0\n",
    "            while st[-1] != '(':\n",
    "                if st.pop() == 't':\n",
    "                    t += 1\n",
    "                else:\n",
    "                    f += 1\n",
    "            st.pop()\n",
    "            op = st.pop()\n",
    "\n",
    "            if op == '!':\n",
    "                st.append('t' if f==1 else 'f')\n",
    "            elif op == '&':\n",
    "                st.append('t' if f == 0 else 'f')\n",
    "            elif op == '|':\n",
    "                st.append('t' if t else 'f')\n",
    "            \n",
    "        return st[-1] == 't'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        stfh = []\n",
    "        sts = []\n",
    "\n",
    "        for s in expression:\n",
    "            if s == '|' or s == '&' or s == '!' :\n",
    "                stfh.append(s)\n",
    "            elif s == ',':\n",
    "                continue\n",
    "            elif s == ')':\n",
    "\n",
    "                if sts[-1] == 'f':\n",
    "                    tmp = False\n",
    "                else:\n",
    "                    tmp = True\n",
    "                sts.pop()\n",
    "                flag = stfh.pop()\n",
    "                print(flag)\n",
    "                print(tmp)\n",
    "                print(sts)\n",
    "                while sts[-1] != '(':\n",
    "                    if sts[-1] == 'f':\n",
    "                        ctmp = False\n",
    "                    else:\n",
    "                        ctmp = True\n",
    "                    sts.pop()\n",
    "                    if flag == '|':\n",
    "                        tmp = tmp or ctmp\n",
    "                    elif flag == '&':\n",
    "                        tmp = tmp and ctmp\n",
    "                sts.pop()\n",
    "                if flag == '!':\n",
    "                    tmp = not tmp\n",
    "                if tmp:\n",
    "                    sts.append('t')\n",
    "                else:\n",
    "                    sts.append('f')\n",
    "                \n",
    "            else:\n",
    "                sts.append(s) \n",
    "        print(sts)\n",
    "        if sts[0] == 'f':\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, exp: str) -> bool:\n",
    "        stack = []\n",
    "        i = 0\n",
    "        while i < len(exp):\n",
    "            c = exp[i]\n",
    "            if c in {\"(\", \",\"}:\n",
    "                i += 1\n",
    "                continue\n",
    "            if c in {\"!\", \"&\", \"|\"}:\n",
    "                stack.append(c)\n",
    "                if c == \"&\":\n",
    "                    stack.append(True)\n",
    "                if c == \"|\":\n",
    "                    stack.append(False)\n",
    "            elif c in {\"f\", \"t\"}:\n",
    "                c_b = True if c == \"t\" else False\n",
    "                if not stack or stack[-1] == \"!\":\n",
    "                    stack.append(c_b)\n",
    "                elif stack[-2] == \"&\":\n",
    "                    stack[-1] &= c_b\n",
    "                elif stack[-2] == \"|\":\n",
    "                    stack[-1] |= c_b\n",
    "            elif c == \")\":\n",
    "                top = stack.pop()\n",
    "                if stack[-1] in {\"&\", \"|\"}:\n",
    "                    stack[-1] = top\n",
    "                else:\n",
    "                    stack[-1] = not top\n",
    "                if len(stack) > 1 and stack[-2] in {True, False}:\n",
    "                    if stack[-3] == \"&\":\n",
    "                        stack[-2] &= stack[-1]\n",
    "                    elif stack[-3] == \"|\":\n",
    "                        stack[-2] |= stack[-1]\n",
    "                    stack.pop()\n",
    "            i += 1\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        d = {\"f\":False, \"t\":True}\n",
    "        expr_st = []\n",
    "        value = [] \n",
    "        n = len(expression)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            c = expression[i]\n",
    "            if c =='!':\n",
    "                expr_st.append(c)\n",
    "                i+=2\n",
    "            elif c=='&':\n",
    "                expr_st.append(c)\n",
    "                value.append(True)\n",
    "                i+=2\n",
    "            elif c=='|':\n",
    "                expr_st.append(c)\n",
    "                value.append(False)\n",
    "                i+=2\n",
    "            elif c=='f' or c=='t':\n",
    "                if expr_st[-1]=='!':\n",
    "                    value.append(d[c])\n",
    "                    i+=1\n",
    "                elif expr_st[-1]=='&':\n",
    "                    value[-1]&=d[c]\n",
    "                    i+=1\n",
    "                elif expr_st[-1]=='|':\n",
    "                    value[-1]|=d[c]\n",
    "                    i+=1\n",
    "            elif c==')':\n",
    "                if expr_st[-1]=='!':\n",
    "                    val = not value.pop()\n",
    "                elif expr_st[-1]=='&' or '|':\n",
    "                    val = value.pop()\n",
    "                expr_st.pop()\n",
    "                \n",
    "                if not expr_st:\n",
    "                    value.append(val)\n",
    "                elif expr_st[-1]=='&':\n",
    "                    value[-1]&=val\n",
    "                elif expr_st[-1]=='|':\n",
    "                    value[-1]|=val\n",
    "                elif expr_st[-1]=='!':\n",
    "                    value.append(val)\n",
    "                i+=1     \n",
    "            else:\n",
    "                i+=1\n",
    "            # print(c, expr_st, value)\n",
    "        return value[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        stk = []\n",
    "        for c in expression:\n",
    "            if c == ',':\n",
    "                continue\n",
    "            if c != ')':\n",
    "                stk.append(c)\n",
    "                continue\n",
    "            t = f = 0\n",
    "            while stk[-1] != '(':\n",
    "                if stk.pop() == 't':\n",
    "                    t += 1\n",
    "                else:\n",
    "                    f += 1\n",
    "            stk.pop()\n",
    "            op = stk.pop()\n",
    "            if op == '!':\n",
    "                stk.append('t' if f == 1 else 'f')\n",
    "            elif op == '&':\n",
    "                stk.append('t' if f == 0 else 'f')\n",
    "            elif op == '|':\n",
    "                stk.append('t' if t else 'f')\n",
    "        return stk[-1] == 't'\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        stk = []\n",
    "        for c in expression:\n",
    "            if c in \"&|!ft\":\n",
    "                stk.append(c)\n",
    "            elif c == \")\":\n",
    "                t = 0\n",
    "                f = 0\n",
    "                while (stk[-1] in \"tf\"):\n",
    "                    if stk[-1] == 'f': f += 1\n",
    "                    else: t += 1\n",
    "                    stk.pop() \n",
    "                fuhao = stk.pop()\n",
    "                if fuhao == \"&\":\n",
    "                    res = 'f' if f > 0 else \"t\"\n",
    "                elif fuhao == \"|\":\n",
    "                    res = \"t\" if t > 0 else \"f\"\n",
    "                else:\n",
    "                    res = \"t\" if f > 0 else \"f\"\n",
    "                stk.append(res)\n",
    "        return stk[0] == 't'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        st = []\n",
    "        for c in expression:\n",
    "            if c in ('!&|(tf'):\n",
    "                st.append(c)\n",
    "            elif c == ')':\n",
    "                t, f = 0, 0\n",
    "                while (e := st.pop()) != '(':\n",
    "                    t += e == 't'\n",
    "                    f += e == 'f'\n",
    "\n",
    "                match st.pop():\n",
    "                    case '!': st.append('t' if f > 0 else 'f')\n",
    "                    case '&': st.append('f' if f > 0 else 't')\n",
    "                    case '|': st.append('t' if t > 0 else 'f')\n",
    "                    \n",
    "        return st[-1] == 't'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        st = []\n",
    "\n",
    "        for c in expression:\n",
    "            if c == ',':\n",
    "                continue\n",
    "            if c != ')':\n",
    "                st.append(c)\n",
    "                continue\n",
    "            f = t = 0\n",
    "            \n",
    "            while st[-1] != '(':\n",
    "                if st.pop() == 'f':\n",
    "                    f += 1\n",
    "                else:\n",
    "                    t += 1\n",
    "            \n",
    "            st.pop()\n",
    "            op = st.pop()\n",
    "\n",
    "            if op == '!':\n",
    "                st.append('t' if f == 1 else 'f')\n",
    "            elif op == '&':\n",
    "                st.append('t' if f == 0 else 'f')\n",
    "            elif op == '|':\n",
    "                st.append('t' if t else 'f')\n",
    "        \n",
    "        return st[-1] == 't'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "\n",
    "        def calc(a, b, op):\n",
    "            x, y = a == 't', b == 't'\n",
    "            ans = x | y if op == '|' else x & y\n",
    "            return 't' if ans else 'f'\n",
    "        \n",
    "        nums = []\n",
    "        ops = []\n",
    "\n",
    "        for c in expression:\n",
    "            if c == ',':\n",
    "                continue\n",
    "            if c == 't' or c == 'f':\n",
    "                nums.append(c)\n",
    "            if c == '|' or c == '&' or c == '!':\n",
    "                ops.append(c)\n",
    "            if c == '(':\n",
    "                nums.append('-')\n",
    "            if c == ')':\n",
    "                op, cur = ops.pop(), \" \"\n",
    "                while nums and nums[-1] != '-':\n",
    "                    top = nums.pop()\n",
    "                    if cur == \" \":\n",
    "                        cur = top\n",
    "                    else:\n",
    "                        cur = calc(cur, top, op)\n",
    "                if op == '!':\n",
    "                    cur = 't' if cur == 'f' else 'f'\n",
    "                nums.pop()\n",
    "                nums.append(cur)\n",
    "        \n",
    "        return nums[-1] == 't'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        stfh = []\n",
    "        sts = []\n",
    "\n",
    "        for s in expression:\n",
    "            if s == '|' or s == '&' or s == '!' :\n",
    "                stfh.append(s)\n",
    "            elif s == ',':\n",
    "                continue\n",
    "            elif s == ')':\n",
    "\n",
    "                if sts[-1] == 'f':\n",
    "                    tmp = False\n",
    "                else:\n",
    "                    tmp = True\n",
    "                sts.pop()\n",
    "                flag = stfh.pop()\n",
    "                # print(flag)\n",
    "                # print(tmp)\n",
    "                # print(sts)\n",
    "                while sts[-1] != '(':\n",
    "                    if sts[-1] == 'f':\n",
    "                        ctmp = False\n",
    "                    else:\n",
    "                        ctmp = True\n",
    "                    sts.pop()\n",
    "                    if flag == '|':\n",
    "                        tmp = tmp or ctmp\n",
    "                    elif flag == '&':\n",
    "                        tmp = tmp and ctmp\n",
    "                sts.pop()\n",
    "                if flag == '!':\n",
    "                    tmp = not tmp\n",
    "                if tmp:\n",
    "                    sts.append('t')\n",
    "                else:\n",
    "                    sts.append('f')\n",
    "                \n",
    "            else:\n",
    "                sts.append(s) \n",
    "        # print(sts)\n",
    "        if sts[0] == 'f':\n",
    "            return False\n",
    "        else:\n",
    "            return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        st = []\n",
    "\n",
    "\n",
    "        for c in expression:\n",
    "            if c == ',':\n",
    "                continue\n",
    "            if c != ')':\n",
    "                st.append(c)\n",
    "                continue\n",
    "            # \")\"情况\n",
    "            t, f = 0, 0\n",
    "            while st and st[-1]!= '(':\n",
    "                if st.pop() == 't':\n",
    "                    t += 1\n",
    "                else:\n",
    "                    f += 1\n",
    "            # 出来后看情况处理\n",
    "            st.pop()\n",
    "            op = st.pop()\n",
    "            if op == '!':\n",
    "                st.append('t' if f == 1 else 'f')\n",
    "            elif op == '&':\n",
    "                st.append('t' if f == 0 else 'f')\n",
    "            elif op == '|':\n",
    "                st.append('t' if t else 'f')\n",
    "        \n",
    "        return st[-1] == 't'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        stack = []\n",
    "        for c in expression:\n",
    "            if c == ',':\n",
    "                continue\n",
    "            # 不是右括号就放入栈\n",
    "            if c != ')':\n",
    "                stack.append(c)\n",
    "                continue\n",
    "            # 是右括号代表需要处理了\n",
    "            t = 0\n",
    "            f = 0\n",
    "            while stack[-1] != '(':\n",
    "                if stack.pop() == 't':\n",
    "                    t += 1\n",
    "                else:\n",
    "                    f += 1\n",
    "            # 弹出左括号\n",
    "            stack.pop()\n",
    "            # 弹出符号\n",
    "            mark = stack.pop()\n",
    "            if mark == '!':\n",
    "                x = 't' if f else 'f'\n",
    "            elif mark == '&':\n",
    "                x = 'f' if f else 't'\n",
    "            else:\n",
    "                x = 't' if t else 'f'\n",
    "            stack.append(x)\n",
    "        return stack[-1] == 't'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        if expression=='t':\n",
    "            return True\n",
    "        if expression=='f':\n",
    "            return False\n",
    "        start,n=expression[0],len(expression)\n",
    "        if start=='!':\n",
    "            return not self.parseBoolExpr(expression[2:n-1])\n",
    "        expression=expression[2:n-1]+','\n",
    "        i,j,count=0,0,0\n",
    "        while i<n-2:\n",
    "            ch=expression[i]\n",
    "            if ch=='(':\n",
    "                count+=1\n",
    "            elif ch==')':\n",
    "                count-=1\n",
    "            elif ch==',' and not count:\n",
    "                b=self.parseBoolExpr(expression[j:i])\n",
    "                if start=='|' and b:\n",
    "                    return True\n",
    "                if start=='&' and not b:\n",
    "                    return False\n",
    "                j=i+1\n",
    "            i+=1\n",
    "        return start==\"&\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "      stack = []\n",
    "      mapping = {\"f\": False, \"t\": True}\n",
    "      for ch in expression:\n",
    "        if ch in mapping:\n",
    "          stack.append(mapping[ch])\n",
    "        elif ch == \",\": continue\n",
    "        elif ch != \")\":\n",
    "          stack.append(ch)\n",
    "        else:\n",
    "          andRes, orRes = True, False\n",
    "          while stack[-1] != \"(\":\n",
    "            cur = stack.pop()\n",
    "            andRes &= cur\n",
    "            orRes |= cur\n",
    "          stack.pop()\n",
    "          if stack[-1] == \"!\":\n",
    "            stack[-1] = not andRes\n",
    "          elif stack[-1] == \"&\":\n",
    "            stack[-1] = andRes\n",
    "          else:\n",
    "            stack[-1] = orRes\n",
    "      return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        stack = []\n",
    "        for i in expression:\n",
    "            if i == ',':\n",
    "                continue\n",
    "            elif i == ')':\n",
    "                seg = []\n",
    "                while stack and stack[-1] != '(':\n",
    "                    b = stack.pop()\n",
    "                    seg.append(1 if b == 't' else 0)\n",
    "\n",
    "                stack.pop()\n",
    "                out = seg[0]\n",
    "                if stack[-1] == '|':\n",
    "                    for a in range(1, len(seg)):\n",
    "                        out = out | seg[a]\n",
    "                elif stack[-1] == '&':\n",
    "                    for a in range(1, len(seg)):\n",
    "                        out = out & seg[a]\n",
    "                elif stack[-1] == '!':\n",
    "                    out = 1 if out == 0 else 0\n",
    "                stack[-1] = 't' if out == 1 else 'f'\n",
    "            else:\n",
    "                stack.append(i)\n",
    "                \n",
    "        return True if stack[0] == 't' else False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        stk = []\n",
    "        for c in expression:\n",
    "            if c in 'tf!&|':\n",
    "                stk.append(c)\n",
    "            elif c == ')':\n",
    "                t = f = 0\n",
    "                while stk[-1] in 'tf':\n",
    "                    t += stk[-1] == 't'\n",
    "                    f += stk[-1] == 'f'\n",
    "                    stk.pop()\n",
    "                match stk.pop():\n",
    "                    case '!':\n",
    "                        c = 't' if f else 'f'\n",
    "                    case '&':\n",
    "                        c = 'f' if f else 't'\n",
    "                    case '|':\n",
    "                        c = 't' if t else 'f'\n",
    "                stk.append(c)\n",
    "        return stk[0] == 't'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        ops,nums = [],[]\n",
    "        def cal(a,b,op):\n",
    "            x,y = a == 't',b == 't'\n",
    "            if op == '|':\n",
    "                ans = x | y\n",
    "            else:\n",
    "                ans = x & y\n",
    "            return 't' if ans else 'f'\n",
    "\n",
    "        for x in expression:\n",
    "            if x == ',':\n",
    "                continue\n",
    "            elif x == '(':\n",
    "                nums.append('-')\n",
    "            elif x == ')':\n",
    "                op = ops.pop()\n",
    "                cur = ''\n",
    "                while nums[-1] != '-':\n",
    "                    t = nums.pop()\n",
    "                    cur = t if not cur else cal(cur,t,op)\n",
    "                if op == '!':\n",
    "                    cur = 't' if cur == 'f' else 'f'\n",
    "                nums.pop()\n",
    "                nums.append(cur)\n",
    "            elif x == 'f' or x == 't':\n",
    "                nums.append(x)\n",
    "            else:# | & !\n",
    "                ops.append(x)\n",
    "        return nums.pop() == 't'\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        stk = []\n",
    "        for c in expression:\n",
    "            if c == ',':\n",
    "                continue\n",
    "            if c != ')':\n",
    "                stk.append(c)\n",
    "                continue\n",
    "            t = f = 0\n",
    "            while stk[-1] != '(':\n",
    "                if stk.pop() == 't':\n",
    "                    t += 1\n",
    "                else:\n",
    "                    f += 1\n",
    "            stk.pop()\n",
    "            op = stk.pop()\n",
    "            if op == '!':\n",
    "                stk.append('t' if f == 1 else 'f')\n",
    "            elif op == '&':\n",
    "                stk.append('t' if f == 0 else 'f')\n",
    "            elif op == '|':\n",
    "                stk.append('t' if t else 'f')\n",
    "        return stk[-1] == 't'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        st = [['&', True]]\n",
    "        for c in expression:\n",
    "            if c == '!':\n",
    "                st.append(['!', None])\n",
    "            elif c == '&':\n",
    "                st.append(['&', True])\n",
    "            elif c == '|':\n",
    "                st.append(['|', False])\n",
    "            \n",
    "            b = None\n",
    "            if c == ')':\n",
    "                e = st.pop()\n",
    "                b = e[1]\n",
    "            elif c in ('t', 'f'):\n",
    "                b = c == 't'\n",
    "            \n",
    "            if b is not None:\n",
    "                e = st[-1]\n",
    "                if e[0] == '!':\n",
    "                    e[1] = not b\n",
    "                elif e[0] == '&':\n",
    "                    e[1] &= b\n",
    "                elif e[0] == '|':\n",
    "                    e[1] |= b\n",
    "        \n",
    "        return st[0][1]        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        st = []\n",
    "        for c in expression:\n",
    "            if c in ('tf!&|('):\n",
    "                st.append(c)\n",
    "            elif c == ')':\n",
    "                t, f = 0, 0\n",
    "                while (e := st.pop()) != '(':\n",
    "                    t += e == 't'\n",
    "                    f += e == 'f'\n",
    "\n",
    "                match st.pop():\n",
    "                    case '!': st.append('t' if f > 0 else 'f')\n",
    "                    case '&': st.append('f' if f > 0 else 't')\n",
    "                    case '|': st.append('t' if t > 0 else 'f')\n",
    "                    \n",
    "        return st[-1] == 't'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        def dfs(l, r):\n",
    "            if l == r:\n",
    "                return expression[l] == 't'\n",
    "            \n",
    "            match expression[l]:\n",
    "                case '!':\n",
    "                    return not dfs(l+2, r-1)\n",
    "                case '&':\n",
    "                    res = True\n",
    "                    l += 2\n",
    "                    i = l + 1\n",
    "                    cnt = 0\n",
    "                    while i < r:\n",
    "                        match expression[i]:\n",
    "                            case ',':\n",
    "                                if not cnt:\n",
    "                                    res = res and dfs(l, i-1)\n",
    "                                    l = i+1\n",
    "                            case '(':\n",
    "                                cnt += 1\n",
    "                            case ')':\n",
    "                                cnt -= 1\n",
    "                        \n",
    "                        i += 1\n",
    "                    res = res and dfs(l, r-1)\n",
    "                    return res\n",
    "                case '|':\n",
    "                    res = False\n",
    "                    l += 2\n",
    "                    i = l + 1\n",
    "                    cnt = 0\n",
    "                    while i < r:\n",
    "                        match expression[i]:\n",
    "                            case ',':\n",
    "                                if not cnt:\n",
    "                                    res = res or dfs(l, i-1)\n",
    "                                    l = i+1\n",
    "                            case '(':\n",
    "                                cnt += 1\n",
    "                            case ')':\n",
    "                                cnt -= 1\n",
    "                        i += 1\n",
    "                    res = res or dfs(l, r-1)\n",
    "                    return res\n",
    "        \n",
    "        return dfs(0, len(expression)-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        stk = []\n",
    "        for c in expression:\n",
    "            if c == ',':\n",
    "                continue\n",
    "            if c != ')':\n",
    "                stk.append(c)\n",
    "                continue\n",
    "            t = f = 0\n",
    "            while stk[-1] != '(':\n",
    "                if stk.pop() == 't':\n",
    "                    t += 1\n",
    "                else:\n",
    "                    f += 1\n",
    "            stk.pop()\n",
    "            op = stk.pop()\n",
    "            if op == '!':\n",
    "                stk.append('t' if f == 1 else 'f')\n",
    "            elif op == '&':\n",
    "                stk.append('t' if f == 0 else 'f')\n",
    "            elif op == '|':\n",
    "                stk.append('t' if t else 'f')\n",
    "        return stk[-1] == 't'\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        stack = []\n",
    "        s = ['|', '&', '!', '(']\n",
    "        for char in expression:\n",
    "            if char == 't':\n",
    "                stack.append(True)\n",
    "            elif char == 'f':\n",
    "                stack.append(False)\n",
    "            elif char in s:\n",
    "                stack.append(char)\n",
    "            elif char == ')':\n",
    "                ope = []\n",
    "                while stack[-1] != '(':\n",
    "                    ope.append(stack.pop())\n",
    "                stack.pop()\n",
    "                tmp = stack.pop()\n",
    "                if tmp == '!':\n",
    "                    result = not ope[0]\n",
    "                elif tmp == '&':\n",
    "                    result = all(ope)\n",
    "                elif tmp == '|':\n",
    "                    result = any(ope)\n",
    "                stack.append(result)\n",
    "            elif char == ',':\n",
    "                continue\n",
    "        return stack[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        def evaluate(expr, start):\n",
    "            if expr[start] == 't':\n",
    "                return True, start + 1\n",
    "            elif expr[start] == 'f':\n",
    "                return False, start + 1\n",
    "            elif expr[start] == '!':\n",
    "                res, i = evaluate(expr, start + 2)\n",
    "                return not res, i + 1\n",
    "            elif expr[start] == '&':\n",
    "                res = True\n",
    "                i = start + 2\n",
    "                while expr[i] != ')':\n",
    "                    val, i = evaluate(expr, i)\n",
    "                    res = res and val\n",
    "                    if expr[i] == ',':\n",
    "                        i += 1\n",
    "                return res, i + 1\n",
    "            elif expr[start] == '|':\n",
    "                res = False\n",
    "                i = start + 2\n",
    "                while expr[i] != ')':\n",
    "                    val, i = evaluate(expr, i)\n",
    "                    res = res or val\n",
    "                    if expr[i] == ',':\n",
    "                        i += 1\n",
    "                return res, i + 1\n",
    "\n",
    "        res, _ = evaluate(expression, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        stk = []\n",
    "        for c in expression:\n",
    "            if c == ',':\n",
    "                continue\n",
    "            if c != ')':\n",
    "                stk.append(c)\n",
    "                continue\n",
    "            t = f = 0\n",
    "            while stk[-1] != '(':\n",
    "                if stk.pop() == 't':\n",
    "                    t += 1\n",
    "                else:\n",
    "                    f += 1\n",
    "            stk.pop()\n",
    "            op = stk.pop()\n",
    "            if op == '!':\n",
    "                stk.append('t' if f == 1 else 'f')\n",
    "            elif op == '&':\n",
    "                stk.append('t' if f == 0 else 'f')\n",
    "            elif op == '|':\n",
    "                stk.append('t' if t else 'f')\n",
    "        return stk[-1] == 't'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def parseBoolExpr(self, e: str) -> bool:\r\n",
    "        st=[]\r\n",
    "        i=len(e)-1\r\n",
    "        while i>=0:\r\n",
    "            if e[i]==')':\r\n",
    "                st.append(e[i])\r\n",
    "                i-=1\r\n",
    "                continue\r\n",
    "            if e[i]=='(':\r\n",
    "                op=e[i-1]\r\n",
    "                tmp='('\r\n",
    "                if op=='!':\r\n",
    "                    top=st.pop()\r\n",
    "                    st.pop()\r\n",
    "                    st.append(not top)\r\n",
    "                    i-=2\r\n",
    "                    continue\r\n",
    "                if op=='&':\r\n",
    "                    ans=True\r\n",
    "                    while tmp!=')':\r\n",
    "                        tmp=st.pop()\r\n",
    "                        if ans==True and tmp==False:\r\n",
    "                            ans=False\r\n",
    "                        continue\r\n",
    "                    st.append(ans)\r\n",
    "                    i-=2\r\n",
    "                    continue\r\n",
    "                if op=='|':\r\n",
    "                    ans=False\r\n",
    "                    while tmp!=')':\r\n",
    "                        tmp=st.pop()\r\n",
    "                        if ans==False and tmp==True:\r\n",
    "                            ans=True\r\n",
    "                        continue\r\n",
    "                    st.append(ans)\r\n",
    "                    i-=2\r\n",
    "                    continue\r\n",
    "            if e[i]=='t':\r\n",
    "                st.append(True)\r\n",
    "                i-=1\r\n",
    "                continue\r\n",
    "            if e[i]=='f':\r\n",
    "                st.append(False)\r\n",
    "            # 注意\r\n",
    "            i-=1\r\n",
    "        return st[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "        arr=[]\n",
    "        for x in expression:\n",
    "            if x==',':\n",
    "                continue\n",
    "            elif x=='t':\n",
    "                arr.append(True)\n",
    "            elif x=='f':\n",
    "                arr.append(False)\n",
    "            else:\n",
    "                arr.append(x)\n",
    "\n",
    "        b=[]\n",
    "        while len(arr)>0 or len(b)!=1:\n",
    "            x=arr.pop()\n",
    "            if x=='(':\n",
    "                op=arr.pop()\n",
    "                x=b.pop()\n",
    "                if op=='!':\n",
    "                    res=not x\n",
    "                    x=b.pop()\n",
    "                if op=='&':\n",
    "                    res=True\n",
    "                    while x!= ')':\n",
    "                        res=res and x\n",
    "                        x=b.pop()\n",
    "                if op=='|':\n",
    "                    res=False\n",
    "                    while x!= ')':\n",
    "                        res=res or x\n",
    "                        x=b.pop()\n",
    "                x=res\n",
    "            b.append(x)\n",
    "        return b.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def parseBoolExpr(self, expression: str) -> bool:\n",
    "\n",
    "        def split(s):\n",
    "            ret = []\n",
    "            flag = 0\n",
    "            tmp = \"\"\n",
    "            for i in range(len(s)):\n",
    "                # print(s[i])\n",
    "                if s[i] == ',' and flag == 0:\n",
    "                    ret.append(tmp)\n",
    "                    tmp = \"\"\n",
    "                    continue \n",
    "                \n",
    "                if s[i] == '(':\n",
    "                    flag +=1\n",
    "                elif s[i] == ')':\n",
    "                    flag -= 1\n",
    "                tmp += s[i]\n",
    "            \n",
    "            if tmp != \"\":\n",
    "                ret.append(tmp)\n",
    "            return ret\n",
    "                \n",
    "\n",
    "        def dfs(s):\n",
    "            c = s[0]\n",
    "            if len(s) == 1:\n",
    "                if c == 't':\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            \n",
    "            v = s[2: -1]\n",
    "            l = split(v)\n",
    "            print(l)\n",
    "            res_list = []\n",
    "            for e in l:\n",
    "                print(e)\n",
    "                res_list.append(dfs(e))\n",
    "            \n",
    "            print(res_list)\n",
    "            if c == '!':\n",
    "                return  1^res_list[0]\n",
    "            if c == '&':\n",
    "                return min(res_list)\n",
    "            if c == '|':\n",
    "                return max(res_list)\n",
    "\n",
    "        if  dfs(expression):\n",
    "            return True\n",
    "        else:\n",
    "            return False\n",
    "\n",
    "            \n",
    "                "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
